×
[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。
問題
ACコード
自力で解けたものの実装が遅すぎる・・・！
大体こうやったら良いんだろうな、というのはわりとすぐに思い浮かんだものの、細部まで詰めて実装するのに時間がかかってしまった。
今回桁DPの状態で持つ桁数を、普通の数え方と同じく「下位からi桁目」にしてみた。
自分は桁DPするときは上の桁から見るので、前回桁DPを使った時は「上位からi桁目」としていたのだが、どちらが良いのだろう。
上位からの場合、仮定した最大桁数からi桁になってしまうので、実際のi桁目を取り出しづらいのがちょっと良くないが、遷移が直感的なのがちょっと良い。
下位からの場合、遷移の際に桁を足せば良いのか引けば良いのか少し分かりづらいのがちょっと良くないが、状態の桁数をそのまま実際の桁数に使えるのがちょっと良い。
前回上位からやったときは、i桁目を取り出す関数を作ったのだが、どうもスマートに感じなかったので今回は下位からやってみたのだが、やっぱり遷移の際に桁を足せば良いのか引けば良いのかに少し脳のリソースを取られるのが少し嫌だなぁ。
でもどちらかに明らかな優位性を感じるまではとりあえず下位からでやっていこうと思う。
本題に入って、基本的な方針は色々言った通り桁DP。
全てのAの各桁に1が現れる総数を数え、桁iを0と1にしたときのf(X)の増加量inc[桁][0or1]をそれぞれ計算する。
後は通常通り、今見ている桁と、K以下が確定しているかどうかを状態に持ち、その状態までの合計で桁DPを行いたかった。
しかし、K以下という条件を入れ込むのにかなり苦労した。
今回のように、i桁目が1の時のみ増加ではなく、i桁目が0でも増加する場合、値が0でも想定した最大桁数分の0が蓄積されてしまう。
これを解決するためには、桁をどこから始めれば良いんだろうと結構な時間考えた。
Kの値を最大桁数にしてしまうと、Aがそれ以上だった場合に正しく計算できないのは当然だ。
Aの値を最大桁数にしてしまうと、Kがそれ以上だった場合に、Aの最大桁数とKの最大桁数の間の蓄積されるべき0を計算することができない。
なんやかんやあって、サンプルケースのDPの遷移を観察することで大きく進展した。
最大桁数に依存するのではなく、DPの遷移をもっと詰めるべきだった。
直感的に理解したのでなかなか文章に起こすのが難しいが、K以下が確定した状態の遷移を考えることが正解の鍵だった。
Kを最大桁数limitから見ていき、桁iまで見た段階で未だ1が一度も出ていない(=Kの最大桁数より大きい)場合、dp[i~limit][1]が更新されることはない。
なぜなら全て0なのだから、K以下が確定することはないためである。
未更新であることはつまり、dp[i~limit][1]が初期値のままであることと同じなので、初期値であればK以下が確定した状態は更新しなければ良い。
自分がpの遷移を考える場合、適当に分かりやすい部分を選んで考えることが多い。
K以下が確定しているならi桁目の数は0でも1でも好きな方を選んで良く、これはKのi桁目の値に関係なく行えるから条件式は要らない、と当初考えた。
しかしこれだと、正しい「K以下が確定した場合の合計」ではなかった。
1度でもKの桁に1が現れた(=dp[i+1][1]が初期値ではない)を条件に加えることで正解にたどり着けた。
1つ前の記事ABC118 D Match Matchingでも初期値かどうかで遷移するかどうか決めており、実はこの時もこれに気づくのに時間がかかった。
今までの桁DPでは、桁の値が0の場合は遷移先に変更を行わないようなものがほとんど(全て？)で、ABC138 F CoincidenceのようにMSBも状態に持つのかと最初考えてしまった。
さすがに問題のレベルが違う気がするので考え直したが、KのMSBがまだなら遷移しないというのは部分的に同じだ。
桁の値が0の場合は遷移先に変化がないような桁DPでは、最大桁数より上の桁が0で埋められているため、「桁の値が0なら変更しない」という条件で、「初期値なら遷移しない」という条件も覆えているだけで、本来なら後者の条件も入れるべき(のはず)。
初期値なら遷移しない、というのはDP全般において重要だと感じるのでしっかり覚えておきたい。
YouTubeの解説も見てみたのだが、途中までは同じなのにやっぱり頭良さを感じた。
途中のincを計算するところまでは同じだが、その後。
ある桁を0にするか1にするかによる全体の変化量の違いは、それぞれの増加量ではなくその差となるので、上位の桁から貪欲にとは行かないのはかなり初期の段階で分かったが、その差を保持することで貪欲に求められるとは。
そもそも、初期を0として、「1にするかどうか」という視点の持ち方がなかった。
「0を選ぶか1を選ぶか」とは内容的は変わらないが、差を考えるとそうはいかない。
「良い方を選んだらその差だけ増える」と考えるのではなくて、「1にしたら正負もつけてその差だけ増減する」と考える。
初期が0なので、上位の桁から考えるとある時点でその後はどう選んでも良くなる。
どう選んでも良いなら差がプラスのものを全て選べば良いので貪欲に求められる。
桁DPのような「K以下かどうか」という考え方を活かしつつ貪欲といった感じだろうか。
頭良い。
桁DPの解説も少しだけあったので、K以下が確定した状態を0とするか1とするかも確認できた。
たぶんいつも「確定したら0」としていたのだが、今回桁数を下位からに変えたのも影響して(?)、確定したら0か1どっちにしようとなぜか悩んでにした。
悩んで決めたものは実装中に分からなくなって混乱しそうなのでコメントも残しておいた。
確定していない状況が特殊な分岐が必要になるのだから、やっぱり「確定したら0」が自然だよなぁ。
なぜ混乱したのか。
ACコード
#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) begin(x), end(x)
#ifdef LOCAL
#include "../../Lib/cout_container.hpp"
#define debug(x) cout << #x " => " << (x) << endl
#else
#define debug(x) 0
#endif
using lint = long long;
constexpr int INF = 1 << 29;
constexpr lint INFL = 1LL << 61;
constexpr int MOD = (int)1e9 + 7;
constexpr double EPS = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }
int main(void) {
lint n, k;
cin >> n >> k;
vector<lint> a(n);
rep (i, n) cin >> a[i];
int limit = 1;
while ((1LL << limit) < 1e12) ++limit;
vector<int> digit_num(limit + 1);
rep (i, n) {
rep (j, limit + 1) {
if (a[i] & (1LL << j)) ++digit_num[j];
}
}
// inc[桁数][0or1] = 増加量
vector<vector<lint>> inc(limit + 1, vector<lint>(2));
rep (i, limit + 1) {
inc[i][0] = (1LL << i) * digit_num[i];
inc[i][1] = (1LL << i) * (n - digit_num[i]);
}
// dp[桁数][k以下が未確定or確定] = 合計
vector<vector<lint>> dp(limit + 2, vector<lint>(2));
rrep (i, limit + 1) {
bool big = inc[i][0] < inc[i][1];
if (dp[i + 1][1]) dp[i][1] = dp[i + 1][1] + inc[i][big];
if (k & (1LL << i)) {
dp[i][0] = dp[i + 1][0] + inc[i][1];
dp[i][1] = max(dp[i][1], dp[i + 1][0] + inc[i][0]);
} else {
dp[i][0] = dp[i + 1][0] + inc[i][0];
}
}
cout << max(dp[0][0], dp[0][1]) << endl;
return 0;
}
自力で解けたものの実装が遅すぎる・・・！
大体こうやったら良いんだろうな、というのはわりとすぐに思い浮かんだものの、細部まで詰めて実装するのに時間がかかってしまった。
今回桁DPの状態で持つ桁数を、普通の数え方と同じく「下位からi桁目」にしてみた。
自分は桁DPするときは上の桁から見るので、前回桁DPを使った時は「上位からi桁目」としていたのだが、どちらが良いのだろう。
上位からの場合、仮定した最大桁数からi桁になってしまうので、実際のi桁目を取り出しづらいのがちょっと良くないが、遷移が直感的なのがちょっと良い。
下位からの場合、遷移の際に桁を足せば良いのか引けば良いのか少し分かりづらいのがちょっと良くないが、状態の桁数をそのまま実際の桁数に使えるのがちょっと良い。
前回上位からやったときは、i桁目を取り出す関数を作ったのだが、どうもスマートに感じなかったので今回は下位からやってみたのだが、やっぱり遷移の際に桁を足せば良いのか引けば良いのかに少し脳のリソースを取られるのが少し嫌だなぁ。
でもどちらかに明らかな優位性を感じるまではとりあえず下位からでやっていこうと思う。
本題に入って、基本的な方針は色々言った通り桁DP。
全てのAの各桁に1が現れる総数を数え、桁iを0と1にしたときのf(X)の増加量inc[桁][0or1]をそれぞれ計算する。
後は通常通り、今見ている桁と、K以下が確定しているかどうかを状態に持ち、その状態までの合計で桁DPを行いたかった。
しかし、K以下という条件を入れ込むのにかなり苦労した。
今回のように、i桁目が1の時のみ増加ではなく、i桁目が0でも増加する場合、値が0でも想定した最大桁数分の0が蓄積されてしまう。
これを解決するためには、桁をどこから始めれば良いんだろうと結構な時間考えた。
Kの値を最大桁数にしてしまうと、Aがそれ以上だった場合に正しく計算できないのは当然だ。
Aの値を最大桁数にしてしまうと、Kがそれ以上だった場合に、Aの最大桁数とKの最大桁数の間の蓄積されるべき0を計算することができない。
なんやかんやあって、サンプルケースのDPの遷移を観察することで大きく進展した。
最大桁数に依存するのではなく、DPの遷移をもっと詰めるべきだった。
直感的に理解したのでなかなか文章に起こすのが難しいが、K以下が確定した状態の遷移を考えることが正解の鍵だった。
Kを最大桁数limitから見ていき、桁iまで見た段階で未だ1が一度も出ていない(=Kの最大桁数より大きい)場合、dp[i~limit][1]が更新されることはない。
なぜなら全て0なのだから、K以下が確定することはないためである。
未更新であることはつまり、dp[i~limit][1]が初期値のままであることと同じなので、初期値であればK以下が確定した状態は更新しなければ良い。
自分がpの遷移を考える場合、適当に分かりやすい部分を選んで考えることが多い。
K以下が確定しているならi桁目の数は0でも1でも好きな方を選んで良く、これはKのi桁目の値に関係なく行えるから条件式は要らない、と当初考えた。
しかしこれだと、正しい「K以下が確定した場合の合計」ではなかった。
1度でもKの桁に1が現れた(=dp[i+1][1]が初期値ではない)を条件に加えることで正解にたどり着けた。
1つ前の記事ABC118 D Match Matchingでも初期値かどうかで遷移するかどうか決めており、実はこの時もこれに気づくのに時間がかかった。
今までの桁DPでは、桁の値が0の場合は遷移先に変更を行わないようなものがほとんど(全て？)で、ABC138 F CoincidenceのようにMSBも状態に持つのかと最初考えてしまった。
さすがに問題のレベルが違う気がするので考え直したが、KのMSBがまだなら遷移しないというのは部分的に同じだ。
桁の値が0の場合は遷移先に変化がないような桁DPでは、最大桁数より上の桁が0で埋められているため、「桁の値が0なら変更しない」という条件で、「初期値なら遷移しない」という条件も覆えているだけで、本来なら後者の条件も入れるべき(のはず)。
初期値なら遷移しない、というのはDP全般において重要だと感じるのでしっかり覚えておきたい。
YouTubeの解説も見てみたのだが、途中までは同じなのにやっぱり頭良さを感じた。
途中のincを計算するところまでは同じだが、その後。
ある桁を0にするか1にするかによる全体の変化量の違いは、それぞれの増加量ではなくその差となるので、上位の桁から貪欲にとは行かないのはかなり初期の段階で分かったが、その差を保持することで貪欲に求められるとは。
そもそも、初期を0として、「1にするかどうか」という視点の持ち方がなかった。
「0を選ぶか1を選ぶか」とは内容的は変わらないが、差を考えるとそうはいかない。
「良い方を選んだらその差だけ増える」と考えるのではなくて、「1にしたら正負もつけてその差だけ増減する」と考える。
初期が0なので、上位の桁から考えるとある時点でその後はどう選んでも良くなる。
どう選んでも良いなら差がプラスのものを全て選べば良いので貪欲に求められる。
桁DPのような「K以下かどうか」という考え方を活かしつつ貪欲といった感じだろうか。
頭良い。
桁DPの解説も少しだけあったので、K以下が確定した状態を0とするか1とするかも確認できた。
たぶんいつも「確定したら0」としていたのだが、今回桁数を下位からに変えたのも影響して(?)、確定したら0か1どっちにしようとなぜか悩んでにした。
悩んで決めたものは実装中に分からなくなって混乱しそうなのでコメントも残しておいた。
確定していない状況が特殊な分岐が必要になるのだから、やっぱり「確定したら0」が自然だよなぁ。
なぜ混乱したのか。
PR
コメント